/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：删除倒数第K个节点
 * 思路：首先得找到倒数第K个节点和第k-1个节点，接着就是进行删除节点。注意；头节点的删除即可
 * 优化思路：既然删除一个节点需要前驱和后继两个指针，那么我们就创造一个哑结点来当作头节点的前驱指针，那么每一个节点就都可以删除了
 *         ，接下来就是找到删除的节点了。
 *
 * 超级简单思路：既然是删除倒数第K节点，那么我就用双指针找到这个节点就行了，但是删除得有前驱指针，那么我就要找到倒数第k-1个节点，
 *            直接在头节点的前面添加一个哑结点，那么找到的这个新链表的倒数第K个节点，就是原链表的倒数第K-1个节点，直接进行删除操作即可
 */
public class Test {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 首先得找到倒数第N个节点
        if (head.next == null) {
            return null;
        }
        // 直接排除头节点和尾节点
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        if (len == n) {
            head = head.next;
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (n-1 > 0) {
            fast = fast.next;
            n--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 找到要删除的前一个节点
        fast = head;
        while (fast.next != slow) {
            fast = fast.next;
        }
        fast.next = slow.next;
        return head;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
